package com.company.test26;

import com.company.test24.Heap;

import java.util.Scanner;

/**
 * Created by Administrator on 2016.10.18.
 *
 * 哈夫曼编码树
 */
public class HuffmanCode {
    private Tree huffmanCodeTree;

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        System.out.println("Enter a text");
        String text=input.nextLine();

        int[] counts=getCharacterFrequency(text);
        System.out.printf("%-15s%-15s%-15s%-15s\n",
                "ASCII Code","Character","Frequency","Code");

        Tree tree=getHuffmanCodeTree(counts);
        String[] codes=getCode(tree.root);

        for(int i=0;i<codes.length;i++)
            if(counts[i]!=0)
                System.out.printf("%-15d%-15s%-15d%-15s\n",
                        i,(char)i+"",counts[i],codes[i]);
    }


    //以一个text来建立的编码树
    public HuffmanCode(String text) {
        if(text.length()==0){
            return;
        }

        huffmanCodeTree=getHuffmanCodeTree(getCharacterFrequency(text));
    }

    public static Tree getHuffmanCodeTree(int[] counts){
        Heap<Tree>heap=new Heap<>();

        for(int i=0;i<counts.length;i++){
            if(counts[i]==0){
                continue;
            }
            heap.add(new Tree((char)i,counts[i]));
        }


        while (heap.size()>1){
            Tree t1=heap.remove();
            Tree t2=heap.remove();
            heap.add(new Tree(t1,t2));
        }

        return heap.remove();
    }

    public static int[] getCharacterFrequency(String text){
        int[] characterFrequency=new int[256];

        for(int i=0;i<text.length();i++){
            characterFrequency[text.charAt(i)]++;
        }

        return characterFrequency;
    }

    //返回各个字符的编码：
    public static String[] getCode(Tree.Node node){
        if(node==null){
            return null;
        }

        String[] codes=new String[256];
        assign(node,codes);
        return codes;
    }


    //给编码树进行编码,并且把数据保留到数组中。
    public static void assign(Tree.Node root, String[] codes){
        if(root.left!=null){
            root.left.code=root.code+"0";
            assign(root.left,codes);

            root.right.code=root.code+"1";
            assign(root.right,codes);
        }else {
            codes[(int)root.element]=root.code;
        }
    }

    private static class Tree implements Comparable<Tree>{
        private Node root;

        public Tree(char element,int weight){
            root=new Node(element,weight);
        }

        public Tree(Tree t1,Tree t2){
            root=new Node();
            root.left=t1.root;
            root.right=t2.root;
            root.weight=t1.root.weight+t2.root.weight;
        }

        @Override
        public int compareTo(Tree tree) {
            if(root.weight>tree.root.weight){
                return -1;
            }else if(root.weight==tree.root.weight){
                return 0;
            }else {
                return 1;
            }
        }

        private class Node{
            private char element;
            private Node left;
            private Node right;
            private int weight;
            private String code="";

            public Node(char element,int weight){
                this.element=element;
                this.weight=weight;
            }

            public Node(){

            }
        }
    }
}